{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 309,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import time\n",
    "import random\n",
    "import string\n",
    "from datetime import datetime\n",
    "import signal\n",
    "from typing import List\n",
    "\n",
    "class TimeoutError(Exception):\n",
    "    pass\n",
    "\n",
    "class Timeout:\n",
    "    def __init__(self, seconds, error_message=None):\n",
    "        if error_message is None:\n",
    "            error_message = 'test timed out after {}s.'.format(seconds)\n",
    "        self.seconds = seconds\n",
    "        self.error_message = error_message\n",
    "\n",
    "    def handle_timeout(self, signum, frame):\n",
    "        raise TimeoutError(self.error_message)\n",
    "\n",
    "    def __enter__(self):\n",
    "        signal.signal(signal.SIGALRM, self.handle_timeout)\n",
    "        signal.alarm(self.seconds)\n",
    "\n",
    "    def __exit__(self, exc_type, exc_val, exc_tb):\n",
    "        signal.alarm(0)\n",
    "\n",
    "class Problem(object):\n",
    "    timeout_single = 10\n",
    "    timeout_iteration = 600\n",
    "    def __init__(self):\n",
    "        self.iter = 800\n",
    "        self.expected = None\n",
    "\n",
    "    @staticmethod\n",
    "    def generate_random_list(_range, _length):\n",
    "        random.seed(datetime.now())\n",
    "        return [random.randrange(*_range) for x in range(_length)]\n",
    "\n",
    "    @staticmethod\n",
    "    def generate_random_string(_length, ignorecase=False, uniq=False):\n",
    "        if _length == 0:\n",
    "            return \"\"\n",
    "        letters = string.ascii_letters\n",
    "        if ignorecase:\n",
    "            letters = string.ascii_lowercase\n",
    "        res = ['' for x in range(_length)]\n",
    "        i = 0\n",
    "        while i < _length:\n",
    "            rdm = random.choice(letters)\n",
    "            if uniq and rdm in res:\n",
    "                continue\n",
    "            res[i] = rdm\n",
    "            i += 1\n",
    "        return ''.join(res)\n",
    "\n",
    "    @classmethod\n",
    "    def verify_deco(cls, N):\n",
    "        def _deco(func):\n",
    "            def __deco(*args, **kwargs):\n",
    "                if N == 1:\n",
    "                    print('>>>', '%s.%s' % (cls.__name__, func.__name__), args, kwargs)\n",
    "                    with Timeout(Problem.timeout_single):\n",
    "                        result = func(*args, **kwargs)\n",
    "                    print(result)\n",
    "                    return result\n",
    "                else:\n",
    "                    print('>>> [%d]' % N, '%s.%s' % (cls.__name__, func.__name__), args, kwargs)\n",
    "                    start_time = time.time()\n",
    "                    result = None\n",
    "                    with Timeout(Problem.timeout_iteration):\n",
    "                        for i in range(N):\n",
    "                            result = func(*args, **kwargs)\n",
    "                    print(\"%s (%s sec)\" % (result, time.time() - start_time))\n",
    "                    return result\n",
    "            return __deco\n",
    "        return _deco\n",
    "\n",
    "    def verify_result(self, *args, **kwargs):\n",
    "        solutions = [method_name for method_name in dir(self)\n",
    "                  if callable(getattr(self, method_name)) \\\n",
    "                     and method_name.split('_')[0] == 'solution']\n",
    "        if solutions:\n",
    "            result_set = set()\n",
    "            for solu in solutions:\n",
    "                solution = getattr(self, solu)\n",
    "                result_set.add(self.__class__.verify_deco(1)(solution)(*args, **kwargs))\n",
    "            assert(len(result_set) == 1)\n",
    "            res = list(result_set)[0]\n",
    "            if self.expected is not None:\n",
    "                assert self.expected == res\n",
    "        else:\n",
    "            print(\"Not found solution\")\n",
    "\n",
    "    def verify_performance(self, *args, **kwargs):\n",
    "        solutions = [method_name for method_name in dir(self)\n",
    "                     if callable(getattr(self, method_name)) \\\n",
    "                     and method_name.split('_')[0] == 'solution']\n",
    "        if solutions:\n",
    "            for solu in solutions:\n",
    "                solution = getattr(self, solu)\n",
    "                self.__class__.verify_deco(self.iter)(solution)(*args, **kwargs)\n",
    "        else:\n",
    "            print(\"Not found solution\")\n",
    "\n",
    "    def verify(self, *args, **kwargs):\n",
    "        self.verify_result(*args, **kwargs)\n",
    "        self.verify_performance(*args, **kwargs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 310,
   "metadata": {},
   "outputs": [],
   "source": [
    "#1 https://www.techiedelight.com/longest-common-subsequence/\n",
    "class LongestCommonSubsequence(Problem):\n",
    "    \"\"\"\n",
    "    given two strings, find the longest common subsequence\n",
    "    \"abcdefg\" \"bcjkfi\"\n",
    "    the longest common subsequence will be [b c f]\n",
    "    Output: 3\n",
    "    \"\"\"\n",
    "    def test(self):\n",
    "        A = \"\"\n",
    "        B = \"abchijxyz\"\n",
    "        self.expected = 0\n",
    "        self.verify_result(A, B)\n",
    "\n",
    "        A = \"ABCHIJXYZ\"\n",
    "        B = \"\"\n",
    "        self.expected = 0\n",
    "        self.verify_result(A, B)\n",
    "\n",
    "        A = \"abcdefg\"\n",
    "        B = \"cdebcjkfi\"\n",
    "        self.expected = 4\n",
    "        self.verify_result(A, B)\n",
    "\n",
    "        A = Problem.generate_random_string(random.randint(6,12), ignorecase=False, uniq=True)\n",
    "        B = Problem.generate_random_string(random.randint(6,12), ignorecase=False, uniq=True)\n",
    "        self.expected = None\n",
    "        self.verify(A, B)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_DP(A, B):\n",
    "        dp = [[0 for n in range(len(B) + 1)] for m in range(len(A) + 1)]\n",
    "        for i in range(len(A)):\n",
    "            for j in range(len(B)):\n",
    "                if A[i] == B[j]:\n",
    "                    dp[i + 1][j + 1] = dp[i][j] + 1\n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])\n",
    "        return dp[len(A)][len(B)]\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_recursion(A, B):\n",
    "        \"\"\"\n",
    "        the longest common subsequence will be\n",
    "        case1 a|xxxx vs. a|yyyy\n",
    "        case2 max(a|xxxx vs. Ayyyy or axxxx vs. A|yyyy)\n",
    "        \"\"\"\n",
    "        def helper(A, B, idx1, idx2, count):\n",
    "            if idx1 < 0 or idx2 < 0:\n",
    "                return count\n",
    "            if A[idx1] == B[idx2]:\n",
    "                count += 1\n",
    "                return helper(A, B, idx1-1, idx2-1, count)\n",
    "            else:\n",
    "                return max(helper(A, B, idx1-1, idx2, count), helper(A, B, idx1, idx2-1, count))\n",
    "        return helper(A, B, len(A)-1, len(B)-1, 0)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_find(A, B):\n",
    "        if not (A and B):\n",
    "            return 0\n",
    "        results = list()\n",
    "        for idx1 in range(len(A)):\n",
    "            for idx2 in range(len(B)):\n",
    "                if A[idx1] == B[idx2]:\n",
    "                    res = 1\n",
    "                    found = idx2 + 1\n",
    "                    for i in range(idx1+1, len(A)):\n",
    "                        for j in range(found, len(B)):\n",
    "                            if A[i] == B[j]:\n",
    "                                res += 1\n",
    "                                found = j\n",
    "                    results.append(res)\n",
    "        return max(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 311,
   "metadata": {},
   "outputs": [],
   "source": [
    "#2 https://www.techiedelight.com/shortest-common-supersequence-introduction-scs-length/\n",
    "class ShortestCommonSupersequence(Problem):\n",
    "    \"\"\"\n",
    "    given two strings, find the shortest common supersequence\n",
    "    \"abdfg\" \"bfij\"\n",
    "    the shortest common supersequence will be [a b d f g i j]\n",
    "    Output: 3\n",
    "    \"\"\"\n",
    "    def test(self):\n",
    "        A = \"\"\n",
    "        B = \"abdfg\"\n",
    "        self.expected = 5\n",
    "        self.verify_result(A, B)\n",
    "\n",
    "        A = \"ABDFG\"\n",
    "        B = \"\"\n",
    "        self.expected = 5\n",
    "        self.verify_result(A, B)\n",
    "\n",
    "        A = \"abdfg\"\n",
    "        B = \"bfij\"\n",
    "        self.expected = 7\n",
    "        self.verify_result(A, B)\n",
    "\n",
    "        A = Problem.generate_random_string(random.randint(6,12), ignorecase=False, uniq=True)\n",
    "        B = Problem.generate_random_string(random.randint(6,12), ignorecase=False, uniq=True)\n",
    "        self.expected = None\n",
    "        self.verify(A, B)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_DP(A, B):\n",
    "        if not A:\n",
    "            return len(B)\n",
    "        if not B:\n",
    "            return len(A)\n",
    "        l = len(A+B)\n",
    "        dp = [[0 for n in range(len(B) + 1)] for m in range(len(A) + 1)]\n",
    "        for i in range(len(B) + 1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(len(A) + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(len(A)):\n",
    "            for j in range(len(B)):\n",
    "                if A[i] == B[j]:\n",
    "                    dp[i + 1][j + 1] = dp[i][j] + 1\n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + 1\n",
    "        return dp[len(A)][len(B)]\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_recursion(A, B):\n",
    "        \"\"\"\n",
    "        the shortest common supersequence will be\n",
    "        case1 a|xxxx vs. a|yyyy\n",
    "        case2 max(a|xxxx vs. Ayyyy or axxxx vs. A|yyyy)\n",
    "        \"\"\"\n",
    "        def helper(A, B, idx1, idx2, count):\n",
    "            if idx1 < 0:\n",
    "                return count + idx2 + 1\n",
    "            if idx2 < 0:\n",
    "                return count + idx1 + 1\n",
    "            if A[idx1] == B[idx2]:\n",
    "                return helper(A, B, idx1-1, idx2-1, count+1)\n",
    "            else:\n",
    "                return min(helper(A, B, idx1-1, idx2, count+1), helper(A, B, idx1, idx2-1, count+1))\n",
    "        return helper(A, B, len(A)-1, len(B)-1, 0)\n",
    "\n",
    "#     @staticmethod\n",
    "#     def solution_find(A, B):\n",
    "#         if not (A and B):\n",
    "#             return 0\n",
    "#         results = list()\n",
    "#         for idx1 in range(len(A)):\n",
    "#             for idx2 in range(len(B)):\n",
    "#                 if A[idx1] == B[idx2]:\n",
    "#                     res = 1\n",
    "#                     found = idx2 + 1\n",
    "#                     for i in range(idx1+1, len(A)):\n",
    "#                         for j in range(found, len(B)):\n",
    "#                             if A[i] == B[j]:\n",
    "#                                 res += 1\n",
    "#                                 found = j\n",
    "#                     results.append(res)\n",
    "#         return max(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 312,
   "metadata": {},
   "outputs": [],
   "source": [
    "#3 https://www.techiedelight.com/longest-increasing-subsequence-using-dynamic-programming/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 313,
   "metadata": {},
   "outputs": [],
   "source": [
    "#4 https://www.techiedelight.com/levenshtein-distance-edit-distance-problem/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 314,
   "metadata": {},
   "outputs": [],
   "source": [
    "#5 https://www.techiedelight.com/matrix-chain-multiplication/\n",
    "class MatrixChainMultiplication(Problem):\n",
    "    \"\"\"\n",
    "    matrix_A: 10*30\n",
    "    matrix_B: 30*5\n",
    "    matrix_C: 5*60\n",
    "    nums = [10, 30, 5, 60]\n",
    "\n",
    "    (AB)C : ([10,30] * [30,5]) * [5,60] = [10,5] * [5,60] = [10,60]\n",
    "    10*30*5 + 10*5*60 = 4500\n",
    "\n",
    "    A(BC) : [10,30] * ([30,5] * [5,60]) = [10,30] * [30,60] = [10,60]\n",
    "    30*5*60 + 10*30*60 = 27000\n",
    "\n",
    "    dp[m][n] represents the minimum operation number for matrix multiplication from nums[m] to nums[n]\n",
    "\n",
    "    for example:\n",
    "    dp[0][2] records the only result 10*30*5 = 1500\n",
    "    dp[0][3] = min((dp[0][2]+nums[0]*nums[2]*nums[3]), (nums[0]*nums[1]*nums[3]+dp[1][3]))\n",
    "             = min((10*30*5 + 10*50*60), (10*30*60+30*5*60))\n",
    "             = min(4500, 27000)\n",
    "             = 4500\n",
    "    ...\n",
    "    dp[m][n] = min( (dp[m][n-1] + nums[m]*nums[n-1]*nums[n]), (nums[m]*nums[m+1]*nums[n] + dp[m+1][n])\n",
    "    \"\"\"\n",
    "    def test(self):\n",
    "        nums = list()\n",
    "        self.expected = 0\n",
    "        self.verify_result(nums)\n",
    "\n",
    "        nums = [10, 30, 5, 60]\n",
    "        self.expected = 4500\n",
    "        self.verify_result(nums)\n",
    "\n",
    "        nums = Problem.generate_random_list((1, 100), random.randint(8,13))\n",
    "        self.expected = None\n",
    "        self.verify(nums)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_recursion(nums):\n",
    "        if len(nums) < 3:\n",
    "            return 0\n",
    "        def helper(nums, m, n):\n",
    "            if n - m < 2 or n >= len(nums):\n",
    "                raise RuntimeError(\"illegal m, n: %d, %d\" % (m, n))\n",
    "            if n - m == 2:\n",
    "                return nums[m] * nums[m + 1] * nums[n]\n",
    "            res1 = helper(nums, m, n - 1) + nums[m] * nums[n - 1] * nums[n]\n",
    "            res2 = nums[m] * nums[m + 1] * nums[n] + helper(nums, m + 1, n)\n",
    "            return min(res1, res2)\n",
    "        return helper(nums, 0, len(nums) - 1)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_DP(nums):\n",
    "        l = len(nums)\n",
    "        if l < 3:\n",
    "            return 0\n",
    "        dp = [[sys.maxsize for y in range(l)] for x in range(l)]\n",
    "        for i in range(2, l):\n",
    "            # 0,2 1,3 2,4 ... l-3,l-1\n",
    "            # 0,3 1,4 ... l-4,l-1\n",
    "            for j in range(l-i):\n",
    "                if i == 2:\n",
    "                    dp[j][j+i] = nums[j]*nums[j+1]*nums[j+2]\n",
    "                else:\n",
    "                    dp[j][j+i] = min(nums[j]*nums[j+1]*nums[j+i] + dp[j+1][j+i],\n",
    "                                     dp[j][j+i-1] + nums[j]*nums[j+i-1]*nums[j+i])\n",
    "        return dp[0][l-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "metadata": {},
   "outputs": [],
   "source": [
    "#6 https://www.techiedelight.com/0-1-knapsack-problem/\n",
    "class Knapsack01(Problem):\n",
    "    \"\"\"\n",
    "    Input:\n",
    "    value = [ 20, 5, 10, 40, 15, 25]\n",
    "    weight = [1,2,3,8,7,4]\n",
    "    int W = 10\n",
    "    Output: 60\n",
    "    Explaination: 20+40=60 1+8=9<10\n",
    "    \"\"\"\n",
    "    def test(self):\n",
    "        values = []\n",
    "        weights = []\n",
    "        W = 16\n",
    "        self.expected = 0\n",
    "        self.verify_result(values, weights, W)\n",
    "\n",
    "        values = [20, 5, 10, 40, 15, 25]\n",
    "        weights = [1, 2, 3, 8, 7, 4]\n",
    "        W = 0\n",
    "        self.expected = 0\n",
    "        self.verify_result(values, weights, W)\n",
    "\n",
    "        values = [20, 5, 10, 40, 15, 25]\n",
    "        weights = [1, 2, 3, 8, 7, 4]\n",
    "        W = 16\n",
    "        self.expected = 95\n",
    "        self.verify_result(values, weights, W)\n",
    "\n",
    "        l = random.randint(4, 20)\n",
    "        values = [x*5 for x in Problem.generate_random_list((0,20), l)]\n",
    "        weights = Problem.generate_random_list((1,10), l)\n",
    "        W = random.randint(1, 40)\n",
    "        self.expected = None\n",
    "        self.verify(values, weights, W)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_recursion(value, weight, W):\n",
    "        \"\"\"recursively\"\"\"\n",
    "        def helper(value, weight, W, V, idx, l):\n",
    "            if idx >= l:\n",
    "                return V\n",
    "            if W <= 0:\n",
    "                return V\n",
    "            if weight[idx] > W:\n",
    "                res = helper(value, weight, W, V, idx + 1, l)\n",
    "                return res\n",
    "            res = max(helper(value, weight, W - weight[idx], V + value[idx], idx + 1, l),\n",
    "                      helper(value, weight, W, V, idx + 1, l))\n",
    "            return res\n",
    "        return helper(value, weight, W, 0, 0, len(value))\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_DP(value, weight, W):\n",
    "        \"\"\"DP\"\"\"\n",
    "        if not (value and weight):\n",
    "            return 0\n",
    "        if W <= 0:\n",
    "            return 0\n",
    "        dp = [[0 for idx in range(len(value))] for w in range(W + 1)]\n",
    "        for w in range(1, W + 1):\n",
    "            for idx in range(len(value)):\n",
    "                if w >= weight[idx]:\n",
    "                    if idx == 0:\n",
    "                        dp[w][idx] = value[idx]\n",
    "                    else:\n",
    "                        dp[w][idx] = max(dp[w][idx - 1], max(dp[w - weight[idx]][0:idx]) + value[idx])\n",
    "                else:\n",
    "                    dp[w][idx] = dp[w][idx - 1]\n",
    "        return max(dp[W])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 316,
   "metadata": {},
   "outputs": [],
   "source": [
    "#7 https://www.techiedelight.com/partition-problem/\n",
    "class PartitionProblem(Problem):\n",
    "    \"\"\"\n",
    "    Given a set of positive integers, find if it can be divided into two subsets with equal sum.\n",
    "    Partition problem is special case of Subset Sum Problem which itself is a special case of the Knapsack Problem.\n",
    "    The idea is to calculate sum of all elements in the set.\n",
    "    If sum is odd, we can't divide the array into two sets..\n",
    "    \n",
    "    For example:\n",
    "    S = {3,1,1,2,2,1}\n",
    "    -> {1,1,1,2} and {2,3}\n",
    "    or -> {3,1,1} and {2,2,1}\n",
    "    \"\"\"\n",
    "    def test(self):\n",
    "        nums = [3,1,1,2,2,1]\n",
    "        self.expected = True\n",
    "        self.verify_result(nums)\n",
    "        \n",
    "        nums = []\n",
    "        self.expected = False\n",
    "        self.verify_result(nums)\n",
    "        \n",
    "        nums = [2]\n",
    "        self.expected = False\n",
    "        self.verify_result(nums)\n",
    "        \n",
    "        nums = [1,2,3,4,5]\n",
    "        self.expected = False\n",
    "        self.verify_result(nums)\n",
    "        \n",
    "    @staticmethod\n",
    "    def solution_DP(nums: List[int]):\n",
    "        l: int = len(nums)\n",
    "        if l <= 1:\n",
    "            return False\n",
    "        total = sum(nums)\n",
    "        if total & 1 == 1:\n",
    "            return False\n",
    "        target = total >> 1\n",
    "        # row: num colume: k\n",
    "        dp = [[False for _ in range(target+1)] for _ in range(l)]\n",
    "        i = 0\n",
    "        while i < l:\n",
    "            j = 0\n",
    "            while j <= target:\n",
    "                if nums[i] == j:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    if i != 0:\n",
    "                        if nums[i] < j:\n",
    "                            dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]\n",
    "                        else:\n",
    "                            dp[i][j] = dp[i-1][j]\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 317,
   "metadata": {},
   "outputs": [],
   "source": [
    "#8 https://www.techiedelight.com/rot-cutting/\n",
    "class RodCuttingProblem(Problem):\n",
    "    \"\"\"\n",
    "    Given a rod of length n and list of prices of rod of length i where 1 <= i <= n\n",
    "    find the optimal way to cut rod into smaller rods in order to maximize profit...\n",
    "    The idea is very simple.\n",
    "    We are given an array price[] where rod of length i has a value price[i-1].\n",
    "    One by one, we partition the given..\n",
    "    \n",
    "    For example:\n",
    "    length[] = [1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    price [] = [1, 5, 8, 9, 10, 17, 17, 20]\n",
    "    Rod length: 4\n",
    "    4                  9\n",
    "    1, 3              (1 + 8) = 9\n",
    "    2, 2              (5 + 5) = 10\n",
    "    3, 1              (8 + 1) = 9\n",
    "    1, 1, 2           (1 + 1 + 5) = 7\n",
    "    1, 2, 1           (1 + 5 + 1) = 7\n",
    "    2, 1, 1           (5 + 1 + 1) = 7\n",
    "    1, 1, 1, 1        (1 + 1 + 1 + 1) = 4\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 318,
   "metadata": {},
   "outputs": [],
   "source": [
    "#9 https://www.techiedelight.com/coin-change-making-problem-unlimited-supply-coins/\n",
    "class CoinChange(Problem):\n",
    "    \"\"\"\n",
    "    Given an unlimited supply of coins of given denominations\n",
    "    find the minimum number of coins required to get a desired change...\n",
    "    \n",
    "    For example:\n",
    "    S = { 1, 3, 5, 7 }\n",
    "    If desired change is 15, the minimum number of coins required is 3\n",
    "    (7 + 7 + 1) or (5 + 5 + 5) or (3 + 5 + 7)\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 319,
   "metadata": {},
   "outputs": [],
   "source": [
    "#10 https://www.techiedelight.com/word-break-problem/\n",
    "class WordBreak(Problem):\n",
    "    \"\"\"\n",
    "    Given a string and a dictionary of words\n",
    "    determine if string can be segmented into a space-separated sequence of one or more dictionary words.\n",
    "    \n",
    "    Input:\n",
    "    dict[] = { \"this\", \"th\", \"is\", \"famous\", \"Word\", \"break\", \"b\",\n",
    "               \"r\", \"e\", \"a\", \"k\", \"br\", \"bre\", \"brea\", \"ak\", \"problem\" };\n",
    "    string = \"Wordbreakproblem\"\n",
    "    \n",
    "    Output:\n",
    "    Word b r e a k problem\n",
    "    Word b r e ak problem\n",
    "    Word br e a k problem\n",
    "    Word br e ak problem\n",
    "    Word bre a k problem\n",
    "    Word bre ak problem\n",
    "    Word brea k problem\n",
    "    Word break problem\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 320,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Given an array of integers and a target\n",
    "# determine if there is a subsequence whose sum is the target\n",
    "# [1,2,3,4] -> 5\n",
    "# Yes. [2,3] or [1,4]\n",
    "class SubsequenceSum(Problem):\n",
    "    def test(self):\n",
    "        nums = []\n",
    "        target = 0\n",
    "        self.expected = True\n",
    "        self.verify_result(nums, target)\n",
    "\n",
    "        nums = [1, 2, 3, 4, 5, 6]\n",
    "        target = 14\n",
    "        self.expected = True\n",
    "        self.verify_result(nums, target)\n",
    "        \n",
    "        nums = [1, 3, 4]\n",
    "        target = 6\n",
    "        self.expected = False\n",
    "        self.verify_result(nums, target)\n",
    "\n",
    "        l = random.randint(4, 10)\n",
    "        nums = Problem.generate_random_list((1,10), l)\n",
    "        target = random.randint(1, sum(nums))\n",
    "        self.expected = None\n",
    "        self.iter = 2000\n",
    "        self.verify(nums, target)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_recursion(nums, k):\n",
    "        \"\"\"recursively\"\"\"\n",
    "        def helper(nums, i, l, k) -> bool:\n",
    "            if i == l:\n",
    "                if k == 0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            bool1 = helper(nums, i+1, l, k)\n",
    "            bool2 = helper(nums, i+1, l, k-nums[i])\n",
    "            return bool1 or bool2\n",
    "        l = len(nums)\n",
    "        if l == 0:\n",
    "            if k == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        return helper(nums, 0, l, k)\n",
    "\n",
    "    @staticmethod\n",
    "    def solution_DP(nums, k):\n",
    "        \"\"\"DP\"\"\"\n",
    "        l = len(nums)\n",
    "        if l == 0:\n",
    "            if k == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        dp = [[False for _ in range(0, k+1)] for _ in range(l)]\n",
    "        i: int = 0\n",
    "        while i < l:\n",
    "            j: int = 0\n",
    "            while j <= k:\n",
    "                if nums[i] == j:\n",
    "                    # print(\"=-=0 dp[%d][%d] = True\" % (i, j))\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    if i != 0:\n",
    "                        if nums[i] < j:\n",
    "                            dp[i][j] = dp[i-1][j-nums[i]] or dp[i-1][j]\n",
    "                            # print(\"=-=1 dp[%d][%d] = dp[%d][%d](%s) or dp[%d][%d](%s)\"%(i,j,i-1,j-nums[i],dp[i-1][j-nums[i]],i-1,j,dp[i-1][j]))\n",
    "                        else:\n",
    "                            dp[i][j] = dp[i-1][j]\n",
    "                            # print(\"=-=2 dp[%d][%d] = dp[%d][%d](%s)\"%(i, j, i - 1, j, dp[i - 1][j]))\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 321,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ">>> PartitionProblem.solution_DP ([3, 1, 1, 2, 2, 1],) {}\n",
      "True\n",
      ">>> PartitionProblem.solution_DP ([],) {}\n",
      "False\n",
      ">>> PartitionProblem.solution_DP ([2],) {}\n",
      "False\n",
      ">>> PartitionProblem.solution_DP ([1, 2, 3, 4, 5],) {}\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "PartitionProblem().test()\n",
    "# SubsequenceSum().test()\n",
    "# ShortestCommonSupersequence().test()\n",
    "# Knapsack01().test()\n",
    "# LongestCommonSubsequence().test()\n",
    "# MatrixChainMultiplication().test()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
